One major requirement for a file system is to keep track of available free space of storage devices in units of blocks. Traditionally, file systems may use a bitmap to represent free space. A bitmap is simply an array of bits, with the Nth bit indicating whether the Nth block is allocated or free. Thus, the overhead of a bitmap may be relatively low, such as, about 0.003% for one bit per 4K size block. For a 1 GB file system, the corresponding bitmap is about 32 KB in size, which may easily fit in memory for quick scanning to identify free space.
However, as sizes of file systems continue to grow faster than the growth of memory sizes, loading a bitmap used in a file system to scan may become non-trivial in either size or time. For example, a 32 GB size bitmap for a 1 PB file system may not fit in memory on most data processing systems or machines. As a result, scanning a bitmap may require reading the bitmap from disk each time (e.g. paged in and out of a disk), which can significantly slow down a file system.
Furthermore, loading a large size bitmap into memory may directly compete with other kernel tasks for finite resources available in a data processing system. For example, if the bitmap cannot be completely cached, a number of buffers may be needed to manage paging operations. Because each buffer may require allocation of one of a finite number of buffer headers in a system, loading a large size bitmap can further degrade system performance.
Thus, traditional file systems that use a bitmap to allocate free space in storage devices do not scale with the growth of modern file systems.